{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Counting Bits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countBits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #比特位计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，对于&nbsp;<code>0 &lt;= i &lt;= n</code> 中的每个 <code>i</code> ，计算其二进制表示中 <strong><code>1</code> 的个数</strong> ，返回一个长度为 <code>n + 1</code> 的数组 <code>ans</code> 作为答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>[0,1,1]\n",
    "<strong>解释：</strong>\n",
    "0 --&gt; 0\n",
    "1 --&gt; 1\n",
    "2 --&gt; 10\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>[0,1,1,2,1,2]\n",
    "<strong>解释：</strong>\n",
    "0 --&gt; 0\n",
    "1 --&gt; 1\n",
    "2 --&gt; 10\n",
    "3 --&gt; 11\n",
    "4 --&gt; 100\n",
    "5 --&gt; 101\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>很容易就能实现时间复杂度为 <code>O(n log n)</code> 的解决方案，你可以在线性时间复杂度 <code>O(n)</code> 内用一趟扫描解决此问题吗？</li>\n",
    "\t<li>你能不使用任何内置函数解决此问题吗？（如，C++ 中的&nbsp;<code>__builtin_popcount</code> ）</li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [counting-bits](https://leetcode.cn/problems/counting-bits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [counting-bits](https://leetcode.cn/problems/counting-bits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        # def pop_count(x):\n",
    "        #     count = 0\n",
    "        #     while x!=0:\n",
    "        #         x &= x -1\n",
    "        #         # x =x >> 1\n",
    "        #         count += 1\n",
    "        #     return count\n",
    "        # ans = [0]*(n+1)\n",
    "        # for x in range(n+1):\n",
    "        #     ans[x] = pop_count(x)\n",
    "        # return ans\n",
    "        ans = [0]*(n+1)\n",
    "        for x in range(1, n+1):\n",
    "            ans[x] = ans[x>>1] + (x&1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "    \n",
    "\n",
    "        by_child =[]\n",
    "        add_child =  [0]\n",
    "        result = [0]\n",
    "        for i in range(1,num+1):\n",
    "            if i % 2 == 0:\n",
    "                \n",
    "                \n",
    "                by_child.append(by_child[0])\n",
    "                add_child.append(by_child[0])\n",
    "                result.append(by_child[0])\n",
    "                \n",
    "                del by_child[0]\n",
    "            else:\n",
    "               \n",
    "                by_child.append(add_child[0] + 1)\n",
    "                result.append(add_child[0] + 1)\n",
    "                del add_child[0]\n",
    "        return result\n",
    "                    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        a = []\n",
    "        for _ in range(num+1):\n",
    "            a.append(bin(_).count('1'))\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "    \n",
    "\n",
    "        by_child =[]\n",
    "        add_child =  [0]\n",
    "        result = [0]\n",
    "        by_head = 0\n",
    "        add_head = 0\n",
    "        is_even = 0\n",
    "        for i in range(1,num+1):\n",
    "            if is_even:\n",
    "                is_even = 0\n",
    "                by_child.append(by_child[by_head])\n",
    "                add_child.append(by_child[by_head])\n",
    "                result.append(by_child[by_head])\n",
    "                by_head += 1 # much faster than del by_child[0]\n",
    "            else:\n",
    "                is_even = 1\n",
    "                by_child.append(add_child[add_head] + 1)\n",
    "                result.append(add_child[add_head] + 1)\n",
    "                add_head += 1\n",
    "        return result\n",
    "                    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if num == 0:\n",
    "            return [num]\n",
    "        res = [0] * (num + 1)\n",
    "        for index in range(1, num+1):\n",
    "            res[index] = res[index // 2] + index % 2\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        values=[0,1]\n",
    "        if(num<=1):\n",
    "            return values[:num+1]\n",
    "        lastIndex=1\n",
    "        for i in range(2,num+1):\n",
    "            if(i==lastIndex*2):\n",
    "                values.append(1)\n",
    "                lastIndex=i\n",
    "            else:\n",
    "                value=1+values[i-lastIndex]\n",
    "                values.append(value)\n",
    "        return values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        list0=[0]\n",
    "        a=1\n",
    "        while a<=num:\n",
    "            a=a*2\n",
    "            list_tmp=[x+1 for x in list0]\n",
    "            list0.extend(list_tmp)\n",
    "        return list0[0:num+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        list1=[0]\n",
    "        while len(list1)<num+1:\n",
    "            list1+=[i+1 for i in list1]\n",
    "            \n",
    "        return list1[:num+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: 'int') -> 'List[int]':\n",
    "        dp = [0, 1]\n",
    "        while len(dp) <= num:\n",
    "            dp.extend([n+1 for n in dp])\n",
    "        \n",
    "        return dp[:num+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        # a=[]\n",
    "        # for i in range(num+1):\n",
    "        #     a.append(bin(i)[2:].count('1'))\n",
    "        # return a\n",
    "        \n",
    "#         观察发现：偶数的二进制中1的个数和其一半的数的二进制个数相等，奇数的二进制中1的个数是其一半的数的二进制中1的个数加1.比如2和4都是1,3和6都是2。5是2,2是1；7是3,3是2.\n",
    "\n",
    "# 另外，整数对应的二进制数逻辑右移一位，就等于除2操作。\n",
    "#         List1 = [0]\n",
    "        \n",
    "#         for i in range(1,num+1):\n",
    "#             #>>1为逻辑右移1位，等于除2操作\n",
    "#             #偶数对2取余为0，奇数对2取余为1\n",
    "#             List1.append(List1[i>>1]+(i%2))\n",
    "            \n",
    "#         return List1\n",
    "\n",
    "\n",
    "#不懂\n",
    "        List1 = [0]\n",
    "        \n",
    "        while(len(List1)<=num):\n",
    "            List2 = [i+1 for i in List1]\n",
    "            List1 = List1 + List2\n",
    "            \n",
    "        return List1[:num+1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        from queue import Queue\n",
    "\n",
    "        by_child = Queue()\n",
    "        add_child =  Queue()\n",
    "        add_child.put((0,0))\n",
    "        result = [0]\n",
    "        for i in range(1,num+1):\n",
    "            if i % 2 == 0:\n",
    "                e = by_child.get()\n",
    "                by_child.put((i,e[1]))\n",
    "                add_child.put((i,e[1]))\n",
    "                result.append(e[1])\n",
    "            else:\n",
    "                e = add_child.get()\n",
    "                by_child.put((e[0],e[1]+1))\n",
    "                result.append(e[1]+1)\n",
    "        \n",
    "        return result\n",
    "                    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: int) -> List[int]:\n",
    "        num_list = [i for i in range(num + 1)]\n",
    "        ans = list(map(numbers_of_one, num_list))\n",
    "        return ans\n",
    "\n",
    "def numbers_of_one(n):\n",
    "    bin_n = bin(n)[2:]\n",
    "    count = 0\n",
    "    for i in bin_n:\n",
    "        if i == '1':\n",
    "            count +=1\n",
    "    return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: int) -> List[int]:\n",
    "        dp=[0]*(num+1)\n",
    "        for i in range(1,num+1):\n",
    "            if(i%2==0):\n",
    "                dp[i]=dp[i//2]\n",
    "            else:\n",
    "                dp[i]=dp[i//2]+1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: int) -> List[int]:\n",
    "        res = [0] * (num + 1)\n",
    "        for i in range(1, num+1):\n",
    "            res[i] = res[i//2] + i % 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: int) -> List[int]:\n",
    "        dp=[1 for i in range(num+1)]\n",
    "        dp[0]=0\n",
    "        for i in range(1,num+1):\n",
    "            if i%2==0:\n",
    "                dp[i]=dp[i//2]\n",
    "            else:\n",
    "                dp[i]=dp[i-1]+1\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: int) -> List[int]:\n",
    "        res = [0]\n",
    "        for i in range(1, num + 1):\n",
    "            if i % 2 == 1:\n",
    "                res.append(res[i-1] + 1)\n",
    "            else:\n",
    "                res.append(res[i>>1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# slolution 4, DP and lowest set bit,\n",
    "# P(i)=P( i&(i-1) ) + 1, use x &= x - 1 to get the lowest set bit,\n",
    "class Solution:\n",
    "    def countBits(self, num: int) -> List[int]:\n",
    "        result = [0 for i in range(num+1)]\n",
    "        for num_i in range(1,num+1):\n",
    "            result[num_i] = result[num_i & (num_i - 1)] + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: int) -> List[int]:\n",
    "        dp = [0 for _ in range(num+1)]\n",
    "        if num>0:\n",
    "            dp[1] = 1\n",
    "        two = 2\n",
    "        pretwo = 0\n",
    "        for i in range(2, num+1):\n",
    "            if i == two:\n",
    "                dp[i] = 1\n",
    "                pretwo = two\n",
    "                two = two*2\n",
    "            else:\n",
    "                dp[i] = 1 + dp[i - pretwo]\n",
    "\n",
    "        return dp[0:num+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num):\n",
    "        result=[0]\n",
    "        write=1\n",
    "        while True:\n",
    "            if num<write:\n",
    "                result+=[result[i]+1 for i in range(num)]\n",
    "                break\n",
    "            result+=[x+1 for x in result]\n",
    "            num-=write\n",
    "            write*=2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: int) -> List[int]:\n",
    "        # #O(n**2)\n",
    "        # res = []\n",
    "        # for i in range(num + 1):\n",
    "        #     res.append(bin(i).count('1'))\n",
    "        # return res\n",
    "\n",
    "        #O(n)\n",
    "        res = [0,1]\n",
    "        while len(res) < num + 1:\n",
    "            box = [i + 1 for i in res]\n",
    "            res.extend(box)\n",
    "        return res[:num + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, num: int):\n",
    "        result = []\n",
    "        for i in range(num+1):\n",
    "            result.append(bin(i).count('1'))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(n+1):\n",
    "            strI = str(bin(i))\n",
    "            # print(strI)\n",
    "            res = strI.count('1')\n",
    "            ans.append(res)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans = [0]\n",
    "        # 维护一个最高有效位置\n",
    "        mbit = 0\n",
    "        for i in range(1, n+1):\n",
    "            if i & (i-1)==0:\n",
    "                # i是最高有效位\n",
    "                mbit = i\n",
    "            ans.append(ans[i - mbit] + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        res = [0]\n",
    "        for i in range(1, n+1):\n",
    "            res.append(res[i&(i-1)]+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans = [0]*(n+1)\n",
    "        for i in range(n+1):\n",
    "            ans[i] = bin(i).count(\"1\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(n+1):\n",
    "        #     tmp=i\n",
    "        #     count=0\n",
    "        #     while tmp:\n",
    "        #         if int(tmp)&1 :\n",
    "        #             count+=1\n",
    "        #         tmp/=2\n",
    "        #     res[i]=count\n",
    "        # return res\n",
    "            \n",
    "            dp[i]=dp[i>>1]+(i&1)\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int):\n",
    "        max_n = 16\n",
    "        index = 1\n",
    "        multi_index = 1\n",
    "        ans = []\n",
    "        ans.append(0)\n",
    "        ans.append(1)\n",
    "        now_index = 1\n",
    "        for index in range(max_n):\n",
    "            for i1 in range(multi_index):\n",
    "                now_index += 1\n",
    "                ans.append(ans[now_index-multi_index])\n",
    "            for i1 in range(multi_index):\n",
    "                now_index += 1\n",
    "                ans.append(ans[now_index-multi_index]+1)\n",
    "            multi_index *= 2\n",
    "        return ans[:n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        counts = []\n",
    "        \n",
    "        # for i in range(n+1):\n",
    "        #     # 统计一的个数\n",
    "        #     x = 0\n",
    "        #     while i:\n",
    "        #         x +=  i & 1\n",
    "        #         i >>= 1\n",
    "        #     counts.append(x)\n",
    "        # print(counts)\n",
    "\n",
    "\n",
    "        \n",
    "        # return counts\n",
    "\n",
    "        for i in range(n+1):\n",
    "            counts.append(bin(i).count('1'))\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        ans=[0]\n",
    "        for i in range(1,n+1):\n",
    "            if i%2 == 1:\n",
    "                num = ans[i-1]+1\n",
    "            else:\n",
    "                num = ans[i//2]\n",
    "            ans.append(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bin_count(self,n):\n",
    "        dic = {}\n",
    "        mid = list(bin(n))\n",
    "        for i in mid[2:]:\n",
    "            if i in dic:dic[i] += 1\n",
    "            else:dic[i] = 1\n",
    "        return dic['1']\n",
    "\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        result= [0]\n",
    "        for i in range(1,n+1):\n",
    "            result.append(self.bin_count(i))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBits(self, n: int) -> List[int]:\n",
    "        def countone(x):\n",
    "            ans = 0\n",
    "            while(x):\n",
    "                x &=( x-1)\n",
    "                ans += 1\n",
    "            return ans \n",
    "        return [ countone(i) for i in range(n+1)]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
